package leetcode;

/*
51. N 皇后
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例：
输入：4
输出：[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],
 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。
*/

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class problems_051 {
    public static void main(String[] args) {
        System.out.println(new Solution().solveNQueens(4));
    }

    static class Solution {
        private final char node_X = 'x'; // 待处理的点
        private final char node_Q = 'Q'; // 皇后的点
        private final char node_B = '.'; // 空白点
        private int length = 0;
        private List<List<String>> ret = new ArrayList<>();

        public List<List<String>> solveNQueens(int n) {
            length = n;
            // 棋盘初始化
            char[][] data = new char[length][length];
            for (int x = 0; x < length; x++) {
                Arrays.fill(data[x], node_X);
            }
            // 棋盘从第一行开始
            for (int i = 0; i < length; i++) {
                dfs(arrClone(data), 0, i);
            }

            ////
            //for (int i = 0; i < ret.size(); i++) {
            //    System.out.println("----------------------");
            //    System.out.println(ret.get(i));
            //}
            return ret;
        }
        //
        private void dfs(char[][] board, int line, int index) {
            // 不可放置判断
            if (board[line][index] != node_X) return;
            // 放置皇后
            board[line][index] = node_Q;
            // 修改不可处理点
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    if ((line == i || index == j || i + j == line + index || i - j == line - index) && board[i][j] == node_X) {
                        board[i][j] = node_B;
                    }
                }
            }
//            sout(board);
            if(line == length - 1){
                List<String> data = new ArrayList<>();
                for (int i = 0; i < length; i++) {
                    data.add(new String(board[i]));
                }
                ret.add(data);
            }else {
                // 棋盘同行的可行点
                for (int i = 0; i < board.length; i++) {
                    dfs(arrClone(board), line + 1, i);
                }
            }
        }
        //
        private char[][] arrClone(char[][] src){
            char[][] data = new char[length][length];
            for (int i = 0; i < length; i++) {
                for (int j = 0; j < length; j++) {
                    data[i][j] = src[i][j];
                }
            }
            return data;
        }
        //
        private void sout(char[][] board){
            System.out.println("-------------------------");
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    if(j != 0) System.out.print(",");
                    System.out.print(board[i][j]);
                }
                System.out.println();
            }
        }
    }
}